package main

import (
	"fmt"
	"os"
)

var dirs = []point{
	{-1, 0}, {0, -1}, {1, 0}, {0, 1},
}

func readMaze(filename string) (maze [][]int) {
	file, err := os.Open(filename)
	if err != nil {
		panic(err)
	}
	defer file.Close()
	var col, row int
	fmt.Fscanf(file, "%d %d", &row, &col)
	maze = make([][]int, row)
	for i := range maze {
		maze[i] = make([]int, col)
		for j := range maze[i] {
			fmt.Fscanf(file, "%d", &maze[i][j])
		}
	}
	return
}

type point struct {
	i, j int
}

func (p point) add(r point) point {
	return point{p.i + r.i, p.j + r.j}
}
func (p point) at(grid [][]int) (gval int, exists bool) {
	if p.i < 0 || p.i >= len(grid) {
		return 0, false
	}
	if p.j < 0 || p.j >= len(grid[p.i]) {
		return 0, false
	}
	return grid[p.i][p.j], true
}
func walk(maze [][]int, start, end point) [][]int {
	steps := make([][]int, len(maze))
	for i := range steps {
		steps[i] = make([]int, len(maze[i]))
	}
	Q := []point{start}
	for len(Q) > 0 {
		curr := Q[0]
		Q = Q[1:]
		if curr == end {
			break
		}
		for _, dir := range dirs {
			next := curr.add(dir)
			gval, ok := next.at(maze)
			if !ok || gval == 1 {
				continue
			}
			gval, ok = next.at(steps)
			if !ok || gval != 0 {
				continue
			}
			if next == start {
				continue
			}
			currStep, _ := curr.at(steps)
			steps[next.i][next.j] = currStep + 1
			Q = append(Q, next)
		}
	}
	return steps
}
func sortStep(steps [][]int, end point) (sortedSteps []point) {
	sortedSteps = append(sortedSteps, end)
	lastStep := steps[end.i][end.j] - 1
	curr := end
	for ; lastStep >= 0; lastStep-- {
		for _, dir := range dirs {
			next := curr.add(dir)
			val, ok := next.at(steps)
			if !ok {
				continue
			}
			if val == lastStep {
				sortedSteps = append(sortedSteps, next)
				curr = next
				break
			}
		}

	}

	return sortedSteps
}

func main() {
	maze := readMaze("maze/maze.txt")
	start := point{0, 0}
	end := point{5, 4}
	steps := walk(maze, start, end)
	fmt.Printf(" C%3d%3d%3d%3d%3d\n", 0, 1, 2, 3, 4)
	for i, step := range steps {
		fmt.Printf("R%d", i)
		for _, cell := range step {
			fmt.Printf("%3d", cell)
		}
		fmt.Println()
	}
	sortSteps := sortStep(steps, end)
	fmt.Println(sortSteps)
}
